package com.递归2;

import java.util.*;

/**
 * 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
 *
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 * 给定 N，计算 F(N)。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：2
 * 输出：1
 * 解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/recursion/4wi01/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 斐波那契数 {
    static class Solution {
        public int fib(int N) {
            if (N <= 1) {
                return N;
            }
            return fib(N-1) + fib(N-2);

        }

        /**
         * 使用记忆化技术
         * @param n
         * @return
         */
        public static Map<Integer, Integer> cecheMap = new HashMap<>();
        public static int fib2(int n) {
            if(cecheMap.containsKey(n)){
                return cecheMap.get(n);
            }
            if(n<=0){
               return 0;
            }
            if(n<=2){
              return 1;

            }
            cecheMap.put(n,fib2(n-1)+fib2(n-2));
            return cecheMap.get(n);
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            System.out.println( solution.fib2(40));
            List<Integer> list = new ArrayList<>();
            Collections.addAll(list,1,2,3,4,5);
            Map<Integer,Integer> map = new Hashtable<>();
            map.put(1,1);
            map.get(1);
            map.containsKey(1);
            map.remove(1);

        }
    }
}
